

class Solution:
    def makeStringSorted(self, s: str) -> int:
        pass




# s = list("cba")


def 上一个字符串(s:str)->str:
    n = len(s)
    i = n - 1
    while i > 0 and s[i - 1] <= s[i]:
        i-=1
    if i == 0:
        return
    k = i
    while k < n and s[i-1] > s[k] :
        k+=1
    j=k-1
    s = list(s)
    s[i-1],s[j] = s[j],s[i-1]
    s = s[:i:] + s[-1: i - 1:-1]
    return "".join(s)

s = "caabbccd"
# s = "abc"
last = 上一个字符串(s)
print(s)
print(last)
print(last<s)

def 下一个字符串(s:str)->str:
    n = len(s)
    i = n - 1
    while i > 0 and s[i - 1] >= s[i]:
        i-=1
    if i == 0:
        return
    k = i
    while k < n and s[i-1]<s[k]:
        k+=1
    j=k-1
    s = list(s)
    s[i-1],s[j] = s[j],s[i-1]
    s = s[:i:] + s[-1: i - 1:-1]
    return "".join(s)

s = "bdcccbaa"
# s = "abc"
next = 下一个字符串(s)
print(s)
print(next)
print(next>s)